题目大意
Gas Station
解题思路
贪心法。但其实需要证明，证明详见：
http://bookshadow.com/weblog/2015/08/06/leetcode-gas-station/
看懂证明，才能看懂代码
结论1：若从加油站A出发，恰好无法到达加油站C（只能到达C的前一站）。则A与C之间的任何一个加油站B均无法到达C。
结论2：若储油量总和sum(gas) >= 耗油量总和sum(cost)，则问题一定有解。
代码
1
2
3
4
5
6
7
8
9
10
11
| class Solution:
# @param {integer[]} gas
# @param {integer[]} cost
# @return {integer}
def canCompleteCircuit(self, gas, cost):
start = sums = 0
for x in range(len(gas)):
sums += gas[x] - cost[x]
if sums < 0:
start, sums = x + 1, 0
return start if sum(gas) >= sum(cost) else -1
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution(object):
def canCompleteCircuit(self, gas, cost):
"""
:type gas: List[int]
:type cost: List[int]
:rtype: int
"""
if sum(gas) < sum(cost):
return -1
min_sum, min_index, total = 0, 0, 0
for i in range(len(gas)):
print '----'
total += gas[i] - cost[i]
if min_sum > total:
print 'gg'
min_sum = total
min_index = i + 1
print i, 'total:', total, 'min_sum:', min_sum, 'min_index:', min_index
if total < 0:
return -1
else:
return min_index
|
总结